package SubjectArray;

public class SearchInsert {

/**
 * 难度：简单
 * 
 * 35. 搜索插入位置
 * 	给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
 * 	你可以假设数组中无重复元素。
 * 
 * 示例 1:
 * 	输入: [1,3,5,6], 5
 * 	输出: 2
 * 
 * 示例 2:
 * 	输入: [1,3,5,6], 2
 * 	输出: 1
 * 
 * 示例 3:
 * 	输入: [1,3,5,6], 7
 * 	输出: 4
 * 
 * 示例 4:
 * 	输入: [1,3,5,6], 0
 * 	输出: 0
 *
 * */
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		SearchInsert si = new SearchInsert();
		System.out.println(si.searchInsert1(new int[] { 1, 3, 5, 6 }, 5));
	}

	// 自己写
	public int searchInsert(int[] nums, int target) {
		for (int i = 0; i < nums.length; i++) {
			if (nums[i] >= target)
				return i;
		}
		return nums.length;
	}
	// 方法一：二分查找
	public int searchInsert1(int[] nums, int target) {
		int n = nums.length;
		int left = 0;
		// 定义target在左闭右闭的区间里，[left, right]
		int right = n - 1;
		int ans = n;
		// 当left==right，区间[left, right]依然有效
		while (left <= right) {
			// 防止溢出(如果left，right都很大时) 等同于(left + right)/2
			// mid=(left+right)>>1相当于mid=(left+right)/2
			int mid = left + ((right - left) >> 1);
			if (target <= nums[mid]) {
				ans = mid;
				// target 在左区间，所以[left, middle - 1]
				right = mid - 1;
			} else {
				// target 在右区间，所以[middle + 1, right]
				left = mid + 1;
			}
		}
		return ans;
	}
}
